from typing import List

"""
    给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
    
    示例 1：
        输入：s = "aab"
        输出：[["a","a","b"],["aa","b"]]
"""


class Solution:
    """
        1，没必要继续下去的深度，就直接continue,去查找他的兄弟结点
        2，回溯算法中的begin的理解，组合问题中这个参数很重要
    """
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        tem = []

        def isA(tem):
            pre = 0
            end = len(tem) - 1
            while pre <= end:
                if tem[pre] == tem[end]:
                    pre += 1
                    end -= 1
                    continue
                else:
                    return 0
            return 1

        def backtracking(begin):
            if begin >= len(s):
                ans.append(tem.copy())
                return
            for i in range(begin + 1, len(s) + 1):
                if isA(s[begin:i]):
                    tem.append(s[begin:i])
                else:
                    continue
                backtracking(i)
                tem.pop()

        backtracking(0)
        return ans
